The present invention generally relates to technology of evaluating performance of an integrated circuit such as CMOS (Complementary Metal-Oxide Semiconductor) and LSI (Large Scale Integration) in its design. More particularly, the present invention relates to technology of calculation of delay distribution, and removal and extraction of false paths.
In the VLSI (Very Large Scale Integration) design in deep sub-micron era, it is necessary to take variation in manufacturing process into account in advance so that circuits with required performance are produced with high yield. Like the technology such as OPC (Optical Proximity Correction), variation control by mask shape correction has become possible, and is increasingly required in practical applications. Therefore, the future VLSI physical design requires technology of designing a highly integrated, high performance circuit by setting proper design margins for each transistor in view of the manufacturing variation.
A method for estimating variation in circuit performance such as critical path delay resulting from manufacturing variation is essential to such design technology. Since the distribution of critical path delay is independent of input, statistical static timing analysis can be used as a method for estimating variation in critical path delay.
One method for statistical static timing analysis is to estimate the maximum delay on the assumption that variations in signal transmission time do not have a correlation (disclosed in M. Hashimoto and H. Onodera, “A performance optimization method by gate resizing based on statistical static timing analysis,” Proc. Workshop on Synthesis And System Integration of Mixed Technology (SASIMI 2000), pp. 77–82, 2000).
On the other hand, one method for static timing analysis of a combinational circuit formed from CMOS logic gates is as follows: a given circuit 100 as shown in FIG. 9 is represented by an acyclic graph G=(V, E) 200 as shown in FIG. 10, and in this graph G 200, the maximum delay required to propagate a value “0” or “1” is obtained for each output terminal v.
In FIG. 10, each dashed ellipse 210 corresponds to a primary input terminal and a primary output terminal of the circuit and input/output terminals of a logic gate. A white circle 211 and a black circle 212 in an ellipse 210 corresponding to a terminal v are 0-vertex v0 and 1-vertex v0 of v, respectively, where v0 and v1 indicate that the corresponding terminal v has signal values “0” and “1”, respectively.
Moreover, S indicates a set of sources into which no edge comes, and T is a set of sinks from which no edge goes out. The sources correspond to the primary input terminals, and the sinks correspond to the primary output terminals. Each directed path from a source to a sink in the graph G is referred to as a path. Although the direction of each edge is not shown in FIG. 10, every edge is a directed edge going out from a left vertex and coming into a right vertex.
In FIG. 10, each box 221, 222, 223 represents a logic gate in the circuit 100. The left vertices in each box correspond to the input terminals of the corresponding logic gate, and the right vertices in each box correspond to the output terminal of the corresponding logic gate. Each edge in the box goes out from a vertex representing input of the corresponding logic gate into a vertex representing output thereof. In the case where the box represents a NAND gate or a NOR gate, each edge in the box corresponds to pMOS or nMOS in the corresponding gate. The way to generate the edges is determined according to the type of logic gate. Each edge connecting vertices in different boxes corresponds to an interconnect, and edge e0 going out from 0-vertex of a terminal reaches 0-vertex of another terminal, and edge e1 going out from 1-vertex of a terminal reaches 1-vertex of another terminal.
The true maximum delay required to propagate a value “0” to a terminal v is herein denoted by d0(v), and the true maximum delay required to propagate a value “1” is herein denoted by d(1). Herein, d0(v), d1(v) for each terminal v of the circuit are represented by the longest path lengths d(v0), d(v1) from a sink to v0, v1 on the graph G, respectively. Therefore, the delay required to transmit a signal value from a terminal v to a terminal w is assigned to each edge e=(v, w) as a weight t(e).
Simulation using such an acyclic graph made it possible to conduct timing analysis of a logic circuit by a relatively simple process.
In delay calculation of a signal z in the circuit 100 as shown in FIG. 9, however, if the delays of signals x and y heavily depend on the delay of a signal b, there is a significant correlation between the delays of the signals x and y. If there is variation in interconnect delay, there is also a correlation between the signal transmission delays of fanout of the signal b. Accordingly, the statistical analysis that does not take correlation into account is likely to be inaccurate.
When delay distribution estimation has poor accuracy, it must be ensured that an integrated circuit will operate in a normal condition even under a plurality of worst conditions which are not likely to occur simultaneously in actual situations, resulting in design including excessive margins. This unnecessarily increases the area and costs such as power consumption in the designed integrated circuit.
The conventional methods have additional problems.
The conventional methods include paths that cannot be simulated actually (false paths). This results in excessively increased calculation time, degraded accuracy in delay estimation, and the like.
The false paths can be divided into two types: logical false paths and functional false paths. A logical false path is a path that will not be activated actually since there is no input for logically propagating a signal to that path. A functional false path is a path that will not be activated since there is an input for activating that path but such an input will not be produced actually. For example, in FIG. 11, among the paths passing through two AND gates G1, G6 controlled by complementary signals z, /z, such a path that the input x of the AND gate G1 other than the input z becomes “1” and the output y of the AND gate G6 becomes “1” corresponds to a logical false path. For example, when operation by a series of operating units (X, M, Y) and a series of operating units (A, M, B) is required, the use of a common multiplier M would result in a series of operating units (A, M, Y) or (X, M, B). However, if the specification does not allow simultaneous operation of the operating units, these series of operating units correspond to functional false paths.
It is practically impossible for human beings to find logical false paths in view of the large circuit scale. Therefore, an automatic finding method using a computer is essential.